package c10_quickStart;

import java.util.Arrays;
import java.util.Random;

import static cn.hutool.core.util.ArrayUtil.swap;

/**
 * 优化版冒泡排序
 * 优化：内层循环，比较次数
 * 思想：每轮冒泡，记录最后
 * 交换数据的位置，
 * 并将此位置作为下一轮
 * 比较的边界值
 */
public class Advance_Sort_Bubble {
    public static void main(String[] args) {
        // 生成50个0-500之间的随机数
        int[] arr = new int[50];
        Random random = new Random();
        for (int i = 0; i < arr.length; i++) {
            arr[i] = random.nextInt(501); // 0-500之间
        }
        
        System.out.println("排序前: " + Arrays.toString(arr));
        
        int n= arr.length-1;
        int count=0;
        
        // 记录开始时间
        long startTime = System.currentTimeMillis();
        
        for (int j = 0; j < arr.length-1; j++) {
            int last = 0;
            for (int i = 0; i < n; i++) {
                if (arr[i] > arr[i + 1]) {
                    swap(arr,i,i+1);
                    last=i; // Record the last swapped position
                    count++;
                }
            }
            n=last;
            if(n==0){
                break;
            }
        }
        
        // 记录结束时间并计算耗时
        long endTime = System.currentTimeMillis();
        long duration = endTime - startTime;
        
        System.out.println("比较的次数: "+count);
        System.out.println("排序耗时: " + duration + "毫秒");
        System.out.println("排序后: " + Arrays.toString(arr));
    }

}